1. Field of the Invention
The present invention generally relates to associative memory devices, and more particularly, to an associative memory device having dynamic associative memory cells. The present invention has particular applicability to content addressable memories (CAMs).
2. Description of the Background Art
Retrieval processing of a large amount of data at a high speed has been in greater demand recently. As a functional memory suitable for retrieval processing of a large amount of data, an associative memory called content addressable memory (hereinafter referred to as "CAM") is conventionally known. The CAM detects match between applied retrieval data and stored data to provide an address (referred to as "match address") of the stored data whose match was detected.
Conventionally, a bit serial type CAM, a complete parallel type CAM and the like are known as CAMs. A bit serial type CAM makes comparison of retrieval data with stored data bit by bit. A complete parallel type CAM makes comparison of retrieval data with stored data for all bits in parallel. Therefore, the complete parallel type CAM can carry out a match retrieving operation at the highest speed. In other words, the complete parallel type CAM can operate retrieval processing at a speed which is several hundreds times faster compared to match retrieval processing by conventional software Therefore, the complete parallel type CAM can be applied to various fields such as artificial intelligence, data base system and the like where it is necessary to carry out a match retrieving operation frequently.
However, in order to implement a complete parallel type CAM having practical large storage capacity, some technical problems are left unsolved. One example of the technical problems is that it is difficult to reduce an area occupied by a memory cell on a semiconductor substrate. In other words, since a complete parallel type CAM carries out a match retrieving operation for all bits in parallel between applied retrieval data and stored data, it is necessary for each CAM cell (or each associative memory cell) to include a data storage circuit and a match detecting circuit.
Since a static CAM includes a static latch circuit as a data storage circuit and an EXCLUSIVE NOR circuit as a match detecting circuit, an area occupied by a CAM on a semiconductor substrate is large. Therefore, the storage capacity of a high integration CAM reported so far is at most 20 k bits. In order to reduce the area occupied by the CAM cell on the semiconductor substrate, it is preferable to use a dynamic CAM cell in place of a static CAM cell. The following description is given of a conventionally known dynamic CAM.
A retrieving operation in a CAM will now be described. FIG. 22 is a concept diagram for explaining a retrieving operation in a CAM. For simplicity of description, FIG. 22 shows a CAM cell array 4 of 10-word-by-8-bit configuration. Referring to FIG. 22, the CAM includes the CAM cell array 4, a retrieval data register 2 for applying retrieval data to the CAM cell array 4, a match flag register 5 for retaining a match flag indicative of a retrieval result, and a priority encoder 6.
For example, it is assumed that the memory cell array 4 stores 10-word data shown in FIG. 22. In addition, it is assumed that the retrieval data register 2 applies retrieval data "1011XXXX" to the memory cell array 4. Each "X" indicates that a corresponding bit in the retrieval data is masked. More specifically, less significant four bits of the retrieval data are masked in this example. Therefore, data in the masked less significant four bits don't affect the match detecting result.
Therefore, match is detected between applied retrieval data and each of the third, the sixth and the tenth stored data, and match flags "0" are set in corresponding positions in the match flag register 5, respectively. The match flags are further applied to the priority encoder 6, causing a word of the highest priority of the third, the sixth and the tenth words in this example, that is, the third word having the lowest address in this example to be selected and causing the address "2" thereof to be provided as a match address. It is pointed out that the above-described priority may be determined optionally, although it is predetermined in this example.
FIG. 23 is a schematic diagram of a circuit of a conventional dynamic CAM cell. The circuit shown in FIG. 23 is disclosed in Proceedings of CICC '91, pp. 10-13. Referring to FIG. 23, the dynamic CAM cell includes capacitors 36, 37 for storing data signal electrical charge, NMOS transistors 30, 31 for writing data, NMOS transistors 32, 33 for configuring an EXCLUSIVE NOR circuit, and an NMOS transistor 34 operating as a diode. The data signal electrical charge is stored by the capacitors 36 and 37 and gate capacitance of the transistors 32 and 33. A cell plate voltage Vcp (=Vcc/2) is applied to one electrode of the capacitors 36 and 37. The gates of the transistors 30 and 31 are connected to a word line WL. One electrode of the transistors 30 and 32 is connected to a bit line BL. One electrode of the transistors 31 and 33 is connected to a bit line /BL. One electrode and the gate of the transistor 34 are connected to a match line ML.
FIGS. 24A and 24B are schematic diagrams of circuits for explaining write and read operations in the dynamic CAM cell. FIGS. 25A and 25B are schematic diagrams of circuits for explaining a match detecting operation. Referring to FIGS. 24A, 24B, 25A and 25B, description will be given below of operations of the dynamic CAM cell.
Referring to FIG. 24A, the write operation is carried out as in the following. First, the bit lines BL, /BL are brought to potentials inverted to each other in response to a data signal to be written. Since the word line WL is activated, the potentials of the bit lines BL, /BL are applied to the capacitors 36, 37 through the transistors 30, 31, respectively. The word line WL attains a low level, and the transistors 30 and 31 are turned off, causing the data signal electrical charge to be retained by the capacitors 36 and 37. The potential of the match line ML is maintained at a low level during the write operation.
Referring to FIG. 24B, the read operation is carried out as in the following. First, a bit line pair BL, /BL is discharged, and a high level potential is applied to the match line ML. For example, assuming that the CAM cell stores the data signal shown in FIG. 24B, the transistor 32 is turned on, while the transistor 33 is turned off. Therefore, the bit line BL is caused to be connected to the match line ML through the transistors 32 and 34, resulting in a high level of the potential of the bit line BL. On the other hand, the potential of the bit line /BL is retained at a low level. During the above-described read operation, the word line WL is not activated.
Referring to FIG. 25A, the match detecting operation is carried out as in the following. First, the bit lines BL, /BL and the match line ML are precharged to a high level potential. As one example, it is assumed that data shown in FIG. 25A is stored in the CAM cell, and that retrieval data is applied to the bit lines BL, /BL. More specifically, since match is detected between the stored data and the retrieval data in this case, neither the transistor 32 nor the transistor 33 is turned on, and the potential of the match line ML is remained at a high level.
Conversely, when an inverted retrieval data signal is applied to the bit lines BL, /BL, mismatch is detected between the retrieval data and the stored data. In other words, as shown in FIG. 25B, the transistor 32 is turned on, and the transistor 33 is turned off. Therefore, the match line ML is discharged through the transistors 32 and 34, resulting in attaining a low level. As described above, after applying a retrieval data signal to the bit lines BL, /BL, "match" or "mismatch" may be detected between the retrieval data and the stored data by detecting potential change of the match line ML.
A conventional static CAM cell, not shown, uses a latch circuit for storing data. On the other hand, a dynamic CAM cell includes two capacitors 36 and 37 for storing data as shown in FIG. 23. By using two capacitors 36 and 37 for storing data in place of a latch circuit, the dynamic CAM cell, compared to the static CAM cell, is reduced in the number of necessary elements, and it is, therefore, suitable for high integration of the CAM.
However, a circuit necessary for accessing such a dynamic CAM cell has not been proposed yet, although a circuit of the dynamic CAM cell shown in FIG. 23 has been conventionally known. A different circuit from the static CAM cell using a latch circuit is needed especially because of employment of the two capacitors 36, 37 for storing data.
For example, a periodical refresh operation is needed to prevent stored data from being lost by leakage of electrical charge from the two capacitors 36, 37 which store data signals. Therefore, a refresh circuit which is not provided in the static CAM is needed. However, it has not been known specifically what type of circuit is suitable for the dynamic CAM. In particular, since the dynamic CAM, compared to a general dynamic RAM conventionally known, carried out complicated operations such as a match detecting operation, for example, it was generally difficult to implement a peripheral circuit of the dynamic CAM cell in a simplified circuit configuration.
Enhancement of the yield rate in production which is expected as high integration of the CAM must be taken into consideration. More specifically, although a redundancy circuit for use in a dynamic RAM has been conventionally known, a practical circuit configuration for redundancy use in a dynamic CAM has not been known. Therefore, in order to prevent lowering of the yield rate with high integration of the CAM in the near future, a practical and effective redundancy circuit has been desired.